#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 046. 全排列.py
@time: 2022/1/10 20:07
@desc: https://leetcode-cn.com/problems/permutations/
> 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

@解题思路：
    - 回溯
    - On(n*n!), Os(n)
'''


class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        def backtrack(first):
            if first == n:
                res.append(nums[:])
            for i in range(first, n):
                # 固定first位，依次更替其后面的元素
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]

        n = len(nums)
        res = []
        backtrack(0)
        return res

class Solution2(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        # 访问数组，记录当前元素是否已经固定过
        visited = [False]*n
        def backtrack(path, length):
            if length == n:
                res.append(path)
                return
            for i in range(n):
                if visited[i]: continue
                visited[i] = True
                # 固定nums[i]，继续递归
                backtrack(path+[nums[i]], length+1)
                visited[i] = False
        res = []
        backtrack([], 0)
        return res
